class Solution22 {
    public int count;
    public boolean[] check;
    public int countArrangement(int n) {
        check = new boolean[n+1];
        dfs(n,0);
        return count;
    }

    public void dfs(int n,int pos) {
        if(pos == n) {
            count++;
            return;
        }

        for(int i = 1; i <= n; i++) {
            if(check[i] == false && (i % (pos+1) == 0 || (pos+1) % i == 0)) {
                check[i] = true;
                dfs(n,pos+1);
                check[i] = false;
            }
        }
    }
}